package com.melo.graph;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc DFS深度优先图搜索类
 * @date 2025-04-21
 */
public class DfsGraph extends FsGraph {

    public DfsGraph(int vertexNum) {
        super(vertexNum);
    }

    /**
     * DFS深度优先搜索
     */
    public void dfs() {
        for (int i = 0; i < getVertexNum(); i++) {
            if (!getVisitFlagArr()[i]) {
                // 遍历所有的结点，进行DFS回溯
                dfs(i);
            }
        }
    }

    /**
     * DFS深度优先搜索
     *
     * @param vertexIndex 顶点的下标
     */
    private void dfs(int vertexIndex) {
        // 首先输出该结点
        System.out.print(getVertexByIndex(vertexIndex) + "->");
        // 将结点设置为已经访问
        getVisitFlagArr()[vertexIndex] = true;
        // 查找结点的第一个邻接结点
        int firstNeighborIndex = getFirstNeighbor(vertexIndex);
        while (firstNeighborIndex != -1) {
            if (!getVisitFlagArr()[firstNeighborIndex]) {
                dfs(firstNeighborIndex);
            }
            // 如果邻接结点结点已经被访问过, 则访问后一个顶点
            firstNeighborIndex = getNextNeighbor(vertexIndex, firstNeighborIndex);
        }
    }
}
